package newcoder.mst;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author gh
 * @create 2021-07-26 18:30
 */
class mst0806Hanoi {
    //面试题 08.06. 汉诺塔问题

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }
/*    采用递归的思路
    三要素如下：
    递归结束条件：只剩下最后一个盘子需要移动
    递归函数主功能：
    1.首先将 n-1 个盘子，从第一个柱子移动到第二个柱子
    2.然后将最后一个盘子移动到第三个柱子上
    3.最后将第二个柱子上的 n-1 个盘子，移动到第三个柱子上
    函数的等价关系式：
    f(n,A,B,C) 表示将n个盘子从A移动到C
    f(n,A,B,C)=f(n-1,A,C,B)+f(1,A,B,C)+f(n-1,B,A,C)*/

    public void move(int size, List<Integer> A, List<Integer> B, List<Integer> C) {
        System.out.println("size = " + size + ", A = " + A + ", B = " + B + ", C = " + C);
        if (size == 0) return;
        System.out.println("s2");
        move(size - 1, A, C, B);
        System.out.println("s3");
        C.add(A.remove(A.size() - 1));
        System.out.println("s3");
        move(size - 1, B, A, C);
        System.out.println("s3");
    }

    public static void main(String[] args) {
        List<Integer> A = new ArrayList<>(Arrays.asList(2, 1, 0));
        List<Integer> B = new ArrayList<>(), C = new ArrayList<>();
        System.out.println(A.size());
//        int a = A.remove(A.size()-1);
//        System.out.println("1:"+a);
//        for (Integer o : A){
//            System.out.println(o);
//        }
//
//        int a2 = A.remove(A.size()-1);
//        System.out.println("2:"+a2);
//        for (Integer o : A){
//            System.out.println(o);
//        }
//        B.addAll(A);
//        Integer b1 = B.remove(B.size() - 1);
//
//        System.out.println("b1:" + b1);
//        for (Integer o : B) {
//            System.out.println(o);
//        }
//
//        B.add(3);
//        int a = A.remove(A.size() - 1);
//        System.out.println(a);
//        C.add(A.remove(A.size() - 1));
        System.out.println(C.toString());
        mst0806Hanoi h = new mst0806Hanoi();
        h.hanota(A, B, C);
    }
}
